package com.xylx.interview.algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，
 * 问能否在这个字符串中找到一个长度为m的连续子串，
 * 使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，
 * 未找到返回-1。比如上面这个例子，acbd，3。给定m个可能重复的字符[a, b, d, d]呢？
 */
public class StringFind {

    public static void main(String[] args) {
        String str = "tbcacbdata";
        int index = findStr(str, "abcd");
        System.out.println(index);
    }

    private static int findStr(String str, String sub) {
        int currentIndex = 0;
        while (currentIndex <= str.length() - sub.length()) {
            String temp = str.substring(currentIndex, currentIndex + sub.length());
            //sub不重复，说明字串不可能有重复字符
            if (isUnique1(temp)) {
                //再判断每个字符都包含在temp中
                if (isSameAsCharArray(temp, sub)) {
                    return currentIndex;
                }
            }

            currentIndex++;
        }

        return -1;
    }

    /**
     * 判断两个字符串是否包含相同的字符类型
     *
     * @param temp
     * @param sub
     * @return
     */
    private static boolean isSameAsCharArray(String temp, String sub) {
        char[] chars = sub.toCharArray();
        for (char c : chars) {
            if (temp.indexOf(new Character(c)) < 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 判断一个字符串中是否存在重复字符
     * 利用Set集合来实现
     * 将字符串中的每个字符依次存入Set集合中，Set集合会自动剔除重复元素。
     * 判断Set集合的元素个数是否等于字符串的长度，若相等，则字符串中没有重复的字符。否则，字符串中存在重复的字符
     *
     * @param s
     * @return
     */
    public static boolean isUnique1(String s) {
        Set<Character> set = new HashSet<Character>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            set.add(c);
        }

        return (set.size() == s.length());
    }

    /**
     * 判断一个字符串中是否存在重复字符
     * 将字符串转化为字符数组。
     * 对于每个字符，从字符串的开头检索，得到索引号index1
     * 从字符串的末尾开始索引，得到索引号index2
     * 判断index1是否等于index2
     * 若相等，则字符串中不含重复字符。否则，字符串中含有重复字符。
     *
     * @param s
     * @return
     */
    public static boolean isUnique2(String s) {
        int index1, index2;
        char[] chars = s.toCharArray();
        for (char c : chars) {
            index1 = s.indexOf(c);
            index2 = s.lastIndexOf(c);
            if (index1 != index2) {
                return false;
            }
        }
        
        return true;
    }
}